
//
//  LinkedList_deduplicate.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/8.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension LinkedList where Element: Equatable {
    
    /// 无序链表去重
    public func deduplicate() -> Int {
        let oldSize = _size
        var nd = first
        var i = 1
        while let node = nd?.successor, node !== _trailer  {
            let hitNode = find(node.value!, i, node)
            if hitNode != nil {
                remove(node) // _size减小由remove隐式完成
            } else {
                i += 1
                nd = node // not node.succssor, its done on while condition
            }
        }
        
        return oldSize - _size
    }
}
